Copy

// ----- Modular Arithmetics ---------------------------------------------------
//
// int power(int n, int k, int m)
// -----------------------------------------------------------------------------

int power(int n, int k, int m) {
	int p = 1;
	while (k) {
		if ((k & 1) == 1) p = (1LL * p * n) % m;
		n = (1LL * n * n) % m;
		k >>= 1;
	}
	return p;
}

// -----------------------------------------------------------------------------